POJ - 3167 Cow Patterns

Posted on | In , ,

思路

一道非常好的kmp题。如果我们想要使用kmp的话，模式串一定要是固定的才行，而本题中，我们是要找一个排名串。这一就要用到一个结论：两个排名串相等，当且仅当对于两个排名串其中相同位置的数，他俩之前比他俩小的数字个数相等而且小于等于他俩的数字个数也相等。这样就转化为了固定的模式串的问题。然后我们需要修改makenext这个函数和kmp的匹配函数，因为其中有动态的增加减少，比如我们失配的时候，我们需要减掉一部分不必要的数字前缀（见代码）。为了取得比一个数小的个数和小于等于他的数，我们使用树状数组（也可以枚举）。题意给了数字最大不超过30，我们开一个BIT[30],然后维护这个树状数组。最后的问题就是POJ的g++似乎对cin，cout很不友好啊？我用c++得了ac，用g++居然TLE???真是玄学。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#include <complex>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1) 
#define rson(x) (x<<1+1)
#define sqr(x) ((x)*(x))

using namespace std;
int nexts[25005], a[100005], b[25005],bs[25005],be[25005], n, m,s;
int BIT[30];
void add(int pos, int val) {
	int x = pos;
	while (x < 30) {
		BIT[x] += val;
		x += lowbit(x);
	}
}
int sum(int pos) {
	int x = pos,sum=0;
	while (x > 0) {
		sum += BIT[x];
		x -= lowbit(x);
	}
	return sum;
}
void makenext() {
	int q, k;
	ms(BIT, 0);
	nexts[0] = 0;
	for (q = 1, k = 0;q < m;q++) {
		while (k > 0 && (sum(b[q]) != be[k] || sum(b[q] - 1) != bs[k])) {
			for (int j = q - k;j < q - nexts[k - 1];j++)add(b[j], -1);
			k = nexts[k - 1];
		}
		if ((sum(b[q]) == be[k] && sum(b[q] - 1) == bs[k]))k++;
		nexts[q] = k;
		add(b[q], 1);
	}
}
set<int> kmp() {
	int i, q;
	set<int> ans;
	makenext();
	ms(BIT, 0);
	for (i = 0, q = 0;i < n;i++) {
		while (q > 0 && (sum(a[i]) != be[q] || sum(a[i] - 1) != bs[q])) {
			for (int j = i - q;j < i - nexts[q - 1];j++)add(a[j], -1);
			q = nexts[q - 1];
		}
		if ((sum(a[i]) == be[q] && sum(a[i] - 1) == bs[q]))q++;
		if (q == m) {
			ans.insert(i - q + 2);
			for (int j = i - q+1;j <= i - nexts[q - 1];j++)add(a[j], -1);
			q = nexts[q - 1];
		}
		add(a[i], 1);
	}
	return ans;
}
int main(){
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while (scanf("%d%d%d",&n,&m,&s)!=EOF) {
		ms(BIT, 0);
		for (int i = 0;i < n;i++)scanf("%d", &a[i]);
		for (int i = 0;i < m;i++) {
			scanf("%d", &b[i]);
			be[i] = sum(b[i]),bs[i]=sum(b[i]-1);
			add(b[i], 1);
		}
		set<int> ans=kmp();
		printf("%d\n", (int)ans.size());
		for (set<int>::iterator it = ans.begin();it != ans.end();it++) {
			printf("%d\n", *it);
		}
	}
	return 0;
}